#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 005. 最长回文子串.py
@time: 2022/1/7 19:39
@desc: https://leetcode-cn.com/problems/longest-palindromic-substring/
> 给你一个字符串 s，找到 s 中最长的回文子串。

@解题思路：
    动态规划：
        1. dp[i][j]表示区间[i,j]是否为回文
        2. 单字符本身为回文
        3. 当区间边界左右两边相等时，即s[i]==s[j]。有以下两种情况之一可以使当前区间[i,j]为回文：
            a. 当前区间长度不大于3，即aba或者aa的情况，此时 j-i+1<=3, 也是j-i+1<4 ===> j-i<3
            b. [i+1, j-1]为回文。即dp[i+1][j-1]==True；
        4. t: O(n2), s: O(n2)
'''


class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        if n < 2:
            return s

        max_len = 1
        begin = 0
        # dp[i][j]代表s[i...j]是否是回文
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            # 每个区间为1的都是回文
            dp[i][i] = True

        # 考察长度从2到n
        for L in range(2, n + 1):
            # 去左边界
            for i in range(n):
                # 右边界 L = j - i + 1
                j = L + i - 1
                # 若越界了此次考察结束
                if j >= n:
                    break

                # 考察左右两端是否符合回文特征
                if not s[i] == s[j]:
                    dp[i][j] = False
                else:
                    # 就是说字符串长度不超过3的情况（因长度为 j-i+1<=3 =>j-i+1<4 => j-i<3 ）
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                # 考察是否产生了最新的最大值
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i  # 记录左边界

        return s[begin: begin + max_len]


class Solution02(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        if n < 2: return s
        # dp[i][j]表示s[i..j]是否为回文
        dp = [[False] * n for _ in range(n)]
        # dp[i][i]长度为1的字符都为回文
        for i in range(n):
            dp[i][i] = True

        max_len, begin = 1, 0
        # 长度从2变化到n
        for L in range(2, n + 1):
            # 从0开始，计算s[i,i+L-1]的dp
            # if s[i]==s[j]: dp[i][j] = dp[i+1][j-1] if j-i+1>=3 else True
            # if not s[i]==s[j]: dp[i][j] = False
            for i in range(n):
                # 右边界
                j = i + L - 1
                # 若越界了此次考察结束
                if j >= n: break
                # 两端不相等必不是回文
                if not s[i] == s[j]:
                    dp[i][j] = False
                else:
                    # 长度小于等于2，则必为回文
                    if L <= 2:
                        dp[i][j] = True
                    # 否则根据内部的字符串决定
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                # 更新最值
                if dp[i][j] and L > max_len:
                    max_len = L
                    begin = i
        return s[begin: begin + max_len]
